package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/n-repeated-element-in-size-2n-array/'>在长度 2N 的数组中找出重复 N 次的元素(N-Repeated Element in Size 2N Array)</a>
 * <p>
 * 给你一个整数数组 nums ，该数组具有以下属性：
 *     <ul>
 *         <li>nums.length == 2 * n.</li>
 *         <li>nums 包含 n + 1 个 不同的 元素</li>
 *         <li>nums 中恰有一个元素重复 n 次</li>
 *     </ul>
 * </p>
 * <p>找出并返回重复了 n 次的那个元素。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,2,3,3]
 *      输出：3
 *
 * 示例 2：
 *      输入：nums = [2,1,2,5,3,2]
 *      输出：2
 *
 * 示例 3：
 *      输入：nums = [5,1,5,2,5,3,5,4]
 *      输出：5
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>2 <= n <= 5000</li>
 *         <li>nums.length == 2 * n</li>
 *         <li>0 <= nums[i] <= 10^4</li>
 *         <li>nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/19 14:50
 */
public class LC0961NRepeatedElementInSize2NArray_S {
    static class Solution {
        public int repeatedNTimes(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                if (!set.add(num)) {
                    return num;
                }
            }
            return -1;
        }

        public int repeatedNTimes2(int[] nums) {
            Random random = new Random();
            while (true) {
                int x = random.nextInt(nums.length);
                int y = random.nextInt(nums.length);
                if (x != y && nums[x] == nums[y]) {
                    return nums[x];
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.repeatedNTimes(new int[]{1, 2, 3, 3}));
        System.out.println(solution.repeatedNTimes(new int[]{2, 1, 2, 5, 3, 2}));
        System.out.println(solution.repeatedNTimes(new int[]{5, 1, 5, 2, 5, 3, 5, 4}));

        System.out.println(solution.repeatedNTimes2(new int[]{1, 2, 3, 3}));
        System.out.println(solution.repeatedNTimes2(new int[]{2, 1, 2, 5, 3, 2}));
        System.out.println(solution.repeatedNTimes2(new int[]{5, 1, 5, 2, 5, 3, 5, 4}));
    }
}
